import sys

__author__ = 'st316'
'''
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
几个注意：
中位数在奇数时是中间一个，偶数时是中间两个的平均值
1、每次两边消除同样长度
2、奇数、偶数舍弃两边数字时候的不同考虑
3、左右在偶数时舍弃数字的不同考虑
4、长度为2和任意长度的找中位数时候的方式，找到中间四个
'''


class Solution:
    # @return a float
    def findMedianSortedArrays(self, A, B):
        la = len(A)
        lb = len(B)
        if la == 0 or lb == 0:
            return self.findMin1(A if lb == 0 else B)
        if la == 1 or lb == 1:
            return self.findMin2(A[0] if la == 1 else B[0], B if la == 1 else A)
        if la == 2 and lb == 2:
            return (max(A[0], B[0]) + min(A[1], B[1])) / 2.0
        if la == 2 and lb != 2:
            return self.findMin3(A, B)
        if la != 2 and lb == 2:
            return self.findMin3(B, A)
        ma = la / 2
        mb = lb / 2
        if A[ma] <= B[mb]:
            if la % 2 == 0:
                k = min(ma - 1, lb - mb - 1)
            else:
                k = min(ma, lb - mb - 1)
            return self.findMedianSortedArrays(A[k:], B[:-1 * k])
        if A[ma] > B[mb]:
            if lb % 2 == 0:
                k = min(la - ma - 1, mb - 1)
            else:
                k = min(la - ma - 1, mb)
            return self.findMedianSortedArrays(A[:-1 * k], B[k:])

    def findMin1(self, A):
        l = len(A)
        if l % 2 == 0:
            return (A[l / 2] + A[l / 2 - 1]) / 2.0
        else:
            return A[l / 2] / 1.0

    def findMin2(self, med, B):
        n = len(B)
        if n == 1:
            return (med + B[0]) / 2.0
        if n % 2 == 0:
            a = B[n / 2 - 1]
            b = B[n / 2]
            if med <= a:
                return a
            elif med <= b:
                return med
            else:  # med > b
                return b
        else:
            a, b, c = B[n / 2 - 1], B[n / 2], B[n / 2 + 1]
            if med <= a:
                return (a + b) / 2.0
            elif med <= c:
                return (med + b) / 2.0
            else: # med > c
                return (b + c) / 2.0

    def findMin3(self, A, B):
        n = len(B)
        if n % 2 == 0:
            a = B[n / 2 - 2] if (n / 2 - 2) >= 0 else -1*sys.maxint
            b = B[n / 2 - 1]
            c = B[n / 2]
            d = B[n / 2 + 1] if (n / 2 + 1) <= (n - 1) else sys.maxint
            if A[1] <= b:
                return (b + max(A[1], a)) / 2.0
            elif A[0] <= b:
                return (b + min(A[1], c)) / 2.0
            elif A[0] >= c:
                return (c + min(A[0], d)) / 2.0
            elif A[1] >= c:
                return (c + max(A[0], b)) / 2.0
            else:    # a < A[0] <= A[1] < b
                return (A[0] + A[1]) / 2.0
        else:
            a = B[n / 2 - 1]
            b = B[n / 2]
            c = B[n / 2 + 1]
            if A[0] >= b:
                return min(A[0], c)
            elif A[1] <= b:
                return max(A[1], a)
            else:  # A[0] < b < A[1]
                return b


if __name__ == '__main__':
    s = Solution()
    print s.findMedianSortedArrays([1,5,6], [2,3,4])